/*
 *  Librarie de tipuri de date abstracte (TDA)
 
    Copyright (C) 2007  Catedra de Structuri de Date

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
/**
 @file linkedlist.h
 @author Stefan Bucur
 @brief This header file contains thee structures and functions needed to work
 with doubly-linked lists.

 It contains functions for creating a linked list, destroying it, manipulating
 elements, finding an element, as well as checking a list's size. 
 */

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

struct linkedlist_adt;
struct linkedlist_node;

/**
 @brief Structure representing a doubly-linked list.

 The structure contains pointers to the first and last items in the list as well
as the item count for the list. However, accessing the structure members should
be done only with the appropriate functions.

Element data is stored using a void pointer. Thus, one should note that there is
no way to tell what kind of data is stored in the list or in a particular element
of the list.
 @see See also: LL_New(), LL_Free()
 */
typedef struct linkedlist_adt *LinkedList;

/**
@brief Structure to hold a doubly-linked list iterator.

The structure contains links to the next and previous elements and is used for
navigating in the list and managing element data.

@see See also: LL_Add(), LL_Remove(), LL_Update, LL_Get(), LL_Find(), LL_Begin(), 
LL_End(), LL_Next()
*/
typedef struct linkedlist_node *LinkedListIterator;


/**
@brief Creates a new linked list, with no elements.

The function creates a doubly-linked list structure and reserves memory for it.
No element is created, nor memory reserved for.
@see Adding elements should be done with LL_Add()
*/
LinkedList LL_New();

/**
@brief Destroys the specified linked list.

Memory used by the linked list as well as all elements is freed. Thus, trying
to access the data in a destroyed list (e.g. through a pointer) will most likely
result in a Access violation / segfault.

@param list the list to be destroyed. A \c LinkedList structure.
*/
void LL_Free(LinkedList list);

/**
@brief Returns the size of the linked list.

The function returns the number of elements in the specified linked list. Note
that the function returns the value of the \a count element. Thus, directly
modifying the \a count structure member will lead to inaccurate results.

@param list list whose length is to be returned.
@return the number of elements in the list.
*/
int LL_Size(LinkedList list);

/**
@brief Determines if the list is empty (has no elements), or not.

In fact the function returns the value of the <tt>count == 0</tt> expression.
Thus, directly modifying the \a count structure member will lead to inaccurate
results.

@param list list to be tested.
@return 1 if the list is empty, 0 otherwise.
*/
int LL_Empty(LinkedList list);

/**
@brief Returns an iterator to the first element in the list.

The functions returns aniterator to the first element in the list.

@param list list to get the iterator to the first element of.
@return an iterator to the first element in the list, or \c NULL if the list
is empty.
*/
LinkedListIterator LL_Begin(LinkedList list);

/**
@brief Returns an interator after the last element in the list.

The function returns an iterator at the end of the list. Thus, in this
implementation it always returns \c NULL.

@param list an iterator for this list will be returned.
@return always returns \c NULL.
*/
LinkedListIterator LL_End(LinkedList list);

/**
@brief Returns an iterator to the next element in the list.

The function returns an iterator to the next element in the list. The current
element is given through an interator, obtained through a call to \c LL_Begin()
or subsequent calls to LL_Next().

@param list the list for which the next element is required.
@param it iterator specifying current position in the list.
@return an iterator to the next element in the list or \c NULL if either the 
iterator points to \a LL_End() (is \c NULL), or does not belong to the list.
*/
LinkedListIterator LL_Next(LinkedList list, LinkedListIterator it);

/**
@brief Inserts data in the list, before the specified position.

The function adds the data specified by the \a el void pointer in the list, at
the position specified by the \a it iterator. A new element is created and 
inserted before \a it . If \a it is \c NULL the the element is added at the end
of the list.

The \a el pointer must point to a memory zone which has been already initialized
and holds the data to be stored in the list. The function doesn't make any kind
of verifications regarding the value of \a el .

@param list the list in which to add.
@param it iterator specifying the position to add.
@param *el element data.
*/
void LL_Add(LinkedList list, LinkedListIterator it, void *el);

/**
@brief Removes the specified element from the list.

The function removes the element specified by the iterator \a it from the list
\a list. The memory for the data stored in the element is not freed.

@param list the list from which to remove the element.
@param it iterator specifying the position of the element to be removed.
@return the data stored at the location specified by the iterator. If the
iterator is \c NULL , does not exist in the list, or points to the end of the
list, the function returns \c NULL.
*/
void *LL_Remove(LinkedList list, LinkedListIterator it);

/**
@brief Gets the data stored in the specified element from the list.

The function retrieves data from the list element specified by the iterator
\a it .

@param list the list to retrieve data from.
@param it iterator specifying the position in the list.
@return the data stored at the specified position in the list, or \c NULL if the
iterator is \c NULL or does not belong to the list.
*/
void *LL_Get(LinkedList list, LinkedListIterator it);

/**
@brief Updates the data contained in the specified position from the list.

The function updates the data of the element specified by the iterator \a it .
The old data is discared and the element will point to the new data.

@param list the list to update the data in.
@param it the position of the element whose data is to be updated (replaced).
@param *el \c void* pointer to a memory location containing new data.
*/
void LL_Update(LinkedList list, LinkedListIterator it, void *el);

/**
@brief Searches for data in the list.

The function searches for the data specified by the \a el in the given list.

@note This version of LinkedList uses for comparision strict pointer comparison.
Further versions may include the possibilty to specify a comparator to provide
more flexible searching.

@param list the list in which to search.
@param *el data to search for.
@return returns a \c LinkedListIterator pointing to the position in the list
where the data was found, or \c NULL otherwise.
*/
LinkedListIterator LL_Find(LinkedList list, void *el);



#endif /*LINKEDLIST_H_*/
